package PriorityQueue;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:周次煜
 * Date: 2024-04-13
 * Time：13:39
 */
public class MyPriorityQueue {



    public int[] elem;
    public int usedSize;

    private  static  final  int FAULTMAXSIZE=10;
    public MyPriorityQueue() {
        elem=new int[FAULTMAXSIZE];

    }

    /**
     * 建堆的时间复杂度：
     *
     * @param array
     */
    public void createHeap(int[] array) {
        usedSize=array.length;
        // 初始化堆
        for (int i = 0; i < usedSize; i++) {
            elem[i]=array[i];
        }
        int len= usedSize;
        int pareindex=(usedSize-2)/2;
        // 调整为大堆
        for (int i =pareindex ; i >= 0 ; i--) {
            shiftDown(i,len);
        }
    }

    /**
     *
     * @param parent 是每棵子树的根节点的下标
     * @param len  是每棵子树调整结束的结束条件
     * 向下调整的时间复杂度：O(logn)
     */



    private void shiftDown(int parent,int len) {

        int child=parent*2+1;

        while (child+1 <len && elem[child] > elem[parent]) {
            if (elem[child] < elem[child+1]) {
                child++;
            }
            swapElem(elem,child,parent);
            parent=child;
            child=child*2+1;
        }

    }


    private  void  swapElem(int []array,int begin,int end ) {
        int tmp=array[begin];
        array[begin]=array[end];
        array[end]=tmp;
    }

    /**
     * 入队：仍然要保持是大根堆
     * @param val
     * 先插入到堆尾
     * 利用向上调整为大根堆
     */
    public void push(int val) {
        if (isFull()) {
            elem= Arrays.copyOf(elem,2*elem.length);
        }

        elem[usedSize]=val;
        usedSize++;
        int child= usedSize-1;

        shiftUp(child);


    }

    /**
     * 想上调整为
     * @param child 孩子节点
     *  向上调整
     *  时间复杂度为 o(N*log(N))
     */



    private void shiftUp(int child) {



        int parent=(child-1)/2;
        while (parent >= 0 && elem[child] > elem[parent])  {
            swapElem(elem,parent,child);
            child=parent;


            parent=(parent-1)/2;

        }
    }

    public boolean isFull() {
        return usedSize==elem.length;
    }

    /**
     * 出队【删除】：每次删除的都是优先级高的元素
     * 仍然要保持是大根堆
     */

    public int pollHeap() {
        if (isEmpty()) {
            return -1;
        }

        int ret=elem[0];



        swapElem(elem,0,usedSize-1);
        usedSize--;
        shiftDown(0,usedSize);



        return  ret;
    }

    public boolean isEmpty() {
        return usedSize==0;
    }

    /**
     * 获取堆顶元素
     * @return 返回该对顶第一个元素
     */

    public int peekHeap() {
        if (isEmpty()) {
            return -1;
        }
        return elem[0];
    }

    public  int size() {
        return usedSize;
    }



}